1. Field of the Invention
The present invention relates to a hierarchical storage device (that can be used as a server side device) having a small capacity primary storage device and a large capacity secondary storage device which uses the primary storage device as a cache and its control method, and a data playback device (that can be used as a client side device) for playbacking data of video, audio, etc., stored in a storage device according to a user operation and its control method.
2. Description of the Background Art
Conventionally, as an inexpensive large capacity storage device, a magnetic tape device, an automatic tape changer for magnetic tapes, an automatic disk changer for removable disks, etc., have been used.
Although these storage devices have a large capacity, they are associated with the problem regarding the response time in the case of random access. For example, in the case of tapes, it is necessary to fast forward or rewind a tape up to a position where the necessary data are recorded. Also, in the case of automatic tape or disk changer, it is necessary to exchange media if the necessary data are recorded on a medium that is currently not mounted on a drive.
For these reasons, there has been a proposition of a hierarchical storage device which incorporates the generally known concept of hierarchical memory by using a hard disk or the like with a high transfer performance and a good random access handling as a primary memory while using the above described large capacity storage device as a secondary storage device.
In general, in such a hierarchical storage device, the primary storage device functions as a cache or a prefetch buffer of data stored in the secondary storage device. In the following, the primary storage device will also be referred to as a cache, while the secondary storage device is also referred to as a library.
In the hierarchical storage device, at a time of making an access to the stored data, whether the necessary data are stored in the cache or not is checked first. If the data are stored in the cache, the data on the cache are accessed. If the data are not stored in the cache, the data on the library are accessed while the accessed data are copied into the cache.
At a time of storing data into the cache, if there is no region left on the cache that can be allocated to that data, there is a need to discard some data on the cache and replace it with new data according to some rules. The known examples of this cache replacement algorithm include the following.
(a) LRU (Least Recently Used): Data for which the elapsed time since it is last accessed is longest will be discarded.
(b) FIFO (First In First Out): Data for which the elapsed time since it is stored in the cache is longest will be discarded.
(c) LFU (Least Frequently Used): Data for which the number of accesses is smallest will be discarded.
These schemes are known to operate efficiently with respect to general data accesses empirically and are currently widely used.
Also, as a unit of transfer between the library and the cache, there are a case of managing transfer in units of data and a case of managing transfer in units of segments (or blocks) into which data are subdivide.
There are also some special cache management schemes including a scheme in which all data that have been opened will be stored into the cache, and a scheme in which only top portions of data are always stored in the cache.
Now, realtime stream data such as video data and audio data are sequentially accessed as time elapses. In such a case, once data transfer is started it is possible to guess the order of data that will be accessed until the data transfer is to be stopped next.
In the case of sequentially transferring consecutive segments in this manner, by storing segments to be used subsequently into the cache while transferring some segment from the cache, it is possible to expect either a seeming disappearance or a reduction of a response time at a time of accessing subsequent segments.
On the other hand, at a time of a start of the sequential transfer, if a segment containing a top of the sequential transfer is not stored in the cache, the time required in accessing the segment that is stored in the secondary storage device will directly give the response time.
Consequently, in the case of making an random access with respect to an arbitrary position in a middle of the realtime stream data, for example, the response time will become long if a segment containing this random access point is not stored in the cache. Namely, in this type of use, the cache hit rate for a segment containing the random access point can largely affect the user's convenience in use.
However, when the conventional cache replacement algorithms are employed for this type of use, the segment containing the random access point will be treated as follows.
(a) In LRU, the segment containing the random access point is regarded as being referred to earlier than other segments that are sequentially accessed thereafter, so that the priority level for becoming a target of discarding is higher for the segment containing the random access point.
(b) in FIFO, the segment containing the random access point is regarded as having a region allocated earlier than other segments that are sequentially accessed thereafter, so that the priority level for becoming a target of discarding is higher for the segment containing the random access point.
(c) In LFU, the priority level for becoming a target of discarding is higher for a segment for which the utilization frequency is lower, regardless of whether it is the segment containing the random access point or not. Consequently, the priority level for becoming a target of discarding is higher for the segment containing the random access and having a lower utilization frequency than a segment not containing any random access point and having a higher utilization frequency.
In other words, in the conventional cache replacement algorithm that are originally designed to improve the overall hit rate of the cache, it is impossible to improve the cache hit rate for the segment containing the random access point in the type of use described above, so that it is impossible to reduce the response time at a time of the random access.
Moreover, in order to improve the user's convenience in use at a time of the random access in the type of use that deals with video data or audio data as described above, in addition to a provision to reduce the response time at the data storage device side, it is important to enable a user to easily specify the desired random access point at a data playback operation mechanism.
For example, as an instrument for enabling user operations, recording/playback devices such as those for video and compact disks are now widely spread to most homes. Also, a playback device for reading out audio information or video information from a network and playbacking such information is also becoming widespread.
In these playback devices, a user is required to carry out tedious operations to search out a desired program or scene by using technique such as the fast forward mode, from data stored in the server side or data in a removable storage medium inserted into the playback device.
As a method for resolving the tediousness associated with such operations, the video playback device utilizes a method for recording indexes in the removable storage medium so as to make it easier for a user to search out the desired program or scene, as in VISS (VHS Index Search System) or VASS (VHS Address Search System). Using such a technique, it becomes possible to record a desired playback start position of the user in a removable storage medium, and call up that playback start position later on.
However, in this conventional method, a user is required to add a playback start index by operations according to the user's own discretion, so that there are redundant operational steps in which the user must explicitly add the indexes. Also, it is impossible to enable the user to make a selection from a list of all the recorded playback start indexes.